package com.datastructure.test.modifytwostring;

public class ModifyTwoString {

    public static void main(String[] args) {

    }

    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here

        int len1 = str1.length(); // 获取 str1 的长度
        int len2 = str2.length(); // 获取 str2 的长度
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 别忘了进行初始化
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i * dc;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j * ic;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 如果在当前位置上，str1 和 str2 的字符相等，那么不需要进行任何操作，dp[i][j] = dp[i - 1][j - 1]
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + rc, Math.min(dp[i - 1][j] + dc, dp[i][j - 1] + ic));
                }
            }
        }
        return dp[len1][len2];
    }
}
